Search Results

Documents authored by Paul, Erik

Document
DOI: 10.4230/LIPIcs.STACS.2024.51
Weighted HOM-Problem for Nonnegative Integers

Authors: Andreas Maletti, Andreea-Teodora Nász, and Erik Paul

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
The HOM-problem asks whether the image of a regular tree language under a given tree homomorphism is again regular. It was recently shown to be decidable by Godoy, Giménez, Ramos, and Àlvarez. In this paper, the ℕ-weighted version of this problem is considered and its decidability is proved. More precisely, it is decidable in polynomial time whether the image of a regular ℕ-weighted tree language under a nondeleting, nonerasing tree homomorphism is regular.
Cite as

Andreas Maletti, Andreea-Teodora Nász, and Erik Paul. Weighted HOM-Problem for Nonnegative Integers. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{maletti_et_al:LIPIcs.STACS.2024.51,
  author =	{Maletti, Andreas and N\'{a}sz, Andreea-Teodora and Paul, Erik},
  title =	{{Weighted HOM-Problem for Nonnegative Integers}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{51:1--51:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.51},
  URN =		{urn:nbn:de:0030-drops-197614},
  doi =		{10.4230/LIPIcs.STACS.2024.51},
  annote =	{Keywords: Weighted Tree Automaton, Decision Problem, Subtree Equality Constraint, Tree Homomorphism, HOM-Problem, Weighted Tree Grammar, Weighted HOM-Problem}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.137
Finite Sequentiality of Finitely Ambiguous Max-Plus Tree Automata

Authors: Erik Paul

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We show that the finite sequentiality problem is decidable for finitely ambiguous max-plus tree automata. A max-plus tree automaton is a weighted tree automaton over the max-plus semiring. A max-plus tree automaton is called finitely ambiguous if the number of accepting runs on every tree is bounded by a global constant. The finite sequentiality problem asks whether for a given max-plus tree automaton, there exist finitely many deterministic max-plus tree automata whose pointwise maximum is equivalent to the given automaton.
Cite as

Erik Paul. Finite Sequentiality of Finitely Ambiguous Max-Plus Tree Automata. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 137:1-137:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{paul:LIPIcs.ICALP.2020.137,
  author =	{Paul, Erik},
  title =	{{Finite Sequentiality of Finitely Ambiguous Max-Plus Tree Automata}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{137:1--137:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.137},
  URN =		{urn:nbn:de:0030-drops-125447},
  doi =		{10.4230/LIPIcs.ICALP.2020.137},
  annote =	{Keywords: Weighted Tree Automata, Max-Plus Tree Automata, Finite Sequentiality, Decidability, Finite Ambiguity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.55
Finite Sequentiality of Unambiguous Max-Plus Tree Automata

Authors: Erik Paul

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We show the decidability of the finite sequentiality problem for unambiguous max-plus tree automata. A max-plus tree automaton is called unambiguous if there is at most one accepting run on every tree. The finite sequentiality problem asks whether for a given max-plus tree automaton, there exist finitely many deterministic max-plus tree automata whose pointwise maximum is equivalent to the given automaton.
Cite as

Erik Paul. Finite Sequentiality of Unambiguous Max-Plus Tree Automata. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{paul:LIPIcs.STACS.2019.55,
  author =	{Paul, Erik},
  title =	{{Finite Sequentiality of Unambiguous Max-Plus Tree Automata}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{55:1--55:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.55},
  URN =		{urn:nbn:de:0030-drops-102946},
  doi =		{10.4230/LIPIcs.STACS.2019.55},
  annote =	{Keywords: Weighted Tree Automata, Max-Plus Tree Automata, Finite Sequentiality, Decidability, Ambiguity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.76
A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic

Authors: Manfred Droste and Erik Paul

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We prove a weighted Feferman-Vaught decomposition theorem for disjoint unions and products of finite structures. The classical Feferman-Vaught Theorem describes how the evaluation of a first order sentence in a generalized product of relational structures can be reduced to the evaluation of sentences in the contributing structures and the index structure. The logic we employ for our weighted extension is based on the weighted MSO logic introduced by Droste and Gastin to obtain a Büchi-type result for weighted automata. We show that for disjoint unions and products of structures, the evaluation of formulas from two respective fragments of the logic can be reduced to the evaluation of formulas in the contributing structures. We also prove that the respective restrictions are necessary. Surprisingly, for the case of disjoint unions, the fragment is the same as the one used in the Büchi-type result of weighted automata. In fact, even the formulas used to show that the respective restrictions are necessary are the same in both cases. However, here proving that they do not allow for a Feferman-Vaught-like decomposition is more complex and employs Ramsey's Theorem. We also show how translation schemes can be applied to go beyond disjoint unions and products.
Cite as

Manfred Droste and Erik Paul. A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 76:1-76:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{droste_et_al:LIPIcs.MFCS.2018.76,
  author =	{Droste, Manfred and Paul, Erik},
  title =	{{A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{76:1--76:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.76},
  URN =		{urn:nbn:de:0030-drops-96581},
  doi =		{10.4230/LIPIcs.MFCS.2018.76},
  annote =	{Keywords: Quantitative Logic, Quantitative Model Theory, Feferman-Vaught Theorem, Translation Scheme, Transduction}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.14
Monitor Logics for Quantitative Monitor Automata

Authors: Erik Paul

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
We introduce a new logic called Monitor Logic and show that it is expressively equivalent to Quantitative Monitor Automata.
Cite as

Erik Paul. Monitor Logics for Quantitative Monitor Automata. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{paul:LIPIcs.MFCS.2017.14,
  author =	{Paul, Erik},
  title =	{{Monitor Logics for Quantitative Monitor Automata}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{14:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.14},
  URN =		{urn:nbn:de:0030-drops-81133},
  doi =		{10.4230/LIPIcs.MFCS.2017.14},
  annote =	{Keywords: Quantitative Monitor Automata, Nested Weighted Automata, Monitor Logics, Weighted Logics}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.53
The Equivalence, Unambiguity and Sequentiality Problems of Finitely Ambiguous Max-Plus Tree Automata are Decidable

Authors: Erik Paul

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
We show that the equivalence, unambiguity and sequentiality problems are decidable for finitely ambiguous max-plus tree automata.
Cite as

Erik Paul. The Equivalence, Unambiguity and Sequentiality Problems of Finitely Ambiguous Max-Plus Tree Automata are Decidable. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 53:1-53:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{paul:LIPIcs.MFCS.2017.53,
  author =	{Paul, Erik},
  title =	{{The Equivalence, Unambiguity and Sequentiality Problems of Finitely Ambiguous Max-Plus Tree Automata are Decidable}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{53:1--53:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.53},
  URN =		{urn:nbn:de:0030-drops-81147},
  doi =		{10.4230/LIPIcs.MFCS.2017.53},
  annote =	{Keywords: Tree Automata, Max-Plus Automata, Equivalence, Unambiguity, Sequentiality, Decidability}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact